import functools
class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        n1 = len(word1)
        n2 = len(word2)
        @functools.cache
        def search(t1, t2):
            if t1 < 0 or t2 < 0:
                return max(t1, t2) + 1
            if word1[t1] == word2[t2]:
                return search(t1 - 1, t2 - 1)
            else:
                return min(search(t1 - 1, t2), search(t1, t2 - 1)) + 1
        return search(n1 - 1, n2 - 1)




data = Solution()
word1 = "leetcode"
word2 = "etco"
print(data.minDistance(word1, word2))